<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Matrix Chain Multiplication</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="matrix-chain-multiplication">Matrix Chain Multiplication</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=vgLJZMUfnsU&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=3">https://www.youtube.com/watch?v=vgLJZMUfnsU&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=3</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MatrixMultiplicationCost.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MatrixMultiplicationCost.java</a></li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp2.png" alt="dp2.png"></p>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.dynamic;

<span class="hljs-comment">/**
 * http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MatrixMultiplicationCost</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findCost</span><span class="hljs-params">(<span class="hljs-keyword">int</span> arr[])</span></span>{
        <span class="hljs-keyword">int</span> temp[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[arr.length][arr.length];
        <span class="hljs-keyword">int</span> q = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> l=<span class="hljs-number">2</span>; l &lt; arr.length; l++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt; arr.length - l; i++){
                <span class="hljs-keyword">int</span> j = i + l;
                temp[i][j] = <span class="hljs-number">1000000</span>;
                <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=i+<span class="hljs-number">1</span>; k &lt; j; k++){
                    q = temp[i][k] + temp[k][j] + arr[i]*arr[k]*arr[j];
                    <span class="hljs-keyword">if</span>(q &lt; temp[i][j]){
                        temp[i][j] = q;
                    }
                }
            }
        }
        <span class="hljs-keyword">return</span> temp[<span class="hljs-number">0</span>][arr.length-<span class="hljs-number">1</span>];
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        MatrixMultiplicationCost mmc = <span class="hljs-keyword">new</span> MatrixMultiplicationCost();
        <span class="hljs-keyword">int</span> arr[] = {<span class="hljs-number">4</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">5</span>,<span class="hljs-number">3</span>};
        <span class="hljs-keyword">int</span> cost = mmc.findCost(arr);
        System.out.print(cost);
    }
}
</div></code></pre>
<p>另外一种斜着遍历的模板, 代码和本题无关。</p>
<pre><code class="language-python"><div>    <span class="hljs-keyword">for</span> (l = <span class="hljs-number">2</span>; l &lt;= len; l++) {
        <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>; i &lt;= len - l + <span class="hljs-number">1</span>; i++) {
            j = i + l - <span class="hljs-number">1</span>;
            dp[i][j] = max;
            int sum = prefixSum[j] - prefixSum[i - <span class="hljs-number">1</span>];
            <span class="hljs-keyword">for</span> (k = i; k &lt; j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + <span class="hljs-number">1</span>][j] + sum);
            }
        }
    }
</div></code></pre>
<h1 id="2-optimal-binary-search-tree">2. Optimal Binary Search Tree</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=hgA4xxlVvfQ&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=8">https://www.youtube.com/watch?v=hgA4xxlVvfQ&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=8</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/OptimalTreeSearch.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/OptimalTreeSearch.java</a></li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp5.png" alt="dp5.png"></p>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.dynamic;

<span class="hljs-comment">/**
 * http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">OptimalTreeSearch</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCostRec</span><span class="hljs-params">(<span class="hljs-keyword">int</span> input[],<span class="hljs-keyword">int</span> freq[])</span></span>{
        
        <span class="hljs-keyword">return</span> minCostRec(input,freq,<span class="hljs-number">0</span>,input.length-<span class="hljs-number">1</span>,<span class="hljs-number">1</span>);
    }
    
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCostRec</span><span class="hljs-params">(<span class="hljs-keyword">int</span> input[],<span class="hljs-keyword">int</span> freq[],<span class="hljs-keyword">int</span> low,<span class="hljs-keyword">int</span> high,<span class="hljs-keyword">int</span> level)</span></span>{
        <span class="hljs-keyword">if</span>(low &gt; high){
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        }
        
        <span class="hljs-keyword">int</span> min = Integer.MAX_VALUE;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=low; i &lt;= high; i++){
            <span class="hljs-keyword">int</span> val = minCostRec(input,freq,low,i-<span class="hljs-number">1</span>,level+<span class="hljs-number">1</span>) + 
                    minCostRec(input,freq,i+<span class="hljs-number">1</span>,high,level+<span class="hljs-number">1</span>)
                    + level*freq[i];
            <span class="hljs-keyword">if</span>(val &lt; min){
                min = val;
            }
        }
        <span class="hljs-keyword">return</span> min;
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCost</span><span class="hljs-params">(<span class="hljs-keyword">int</span> input[], <span class="hljs-keyword">int</span> freq[])</span></span>{
        <span class="hljs-keyword">int</span> T[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[input.length][input.length];
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt; T.length; i++){
            T[i][i] = freq[i];
        }
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> l = <span class="hljs-number">2</span>; l &lt;= input.length; l++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt;= input.length-l; i++){
                <span class="hljs-keyword">int</span> j = i + l -<span class="hljs-number">1</span>;
                T[i][j] = Integer.MAX_VALUE;
                <span class="hljs-keyword">int</span> sum = getSum(freq, i, j);
                
                <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=i; k &lt;= j; k++){
                     <span class="hljs-keyword">int</span> val = sum + (k-<span class="hljs-number">1</span> &lt; i ? <span class="hljs-number">0</span> : T[i][k-<span class="hljs-number">1</span>]) +
                            (k+<span class="hljs-number">1</span> &gt; j ? <span class="hljs-number">0</span> : T[k+<span class="hljs-number">1</span>][j]) ;
                     <span class="hljs-keyword">if</span>(val &lt; T[i][j]){
                         T[i][j] = val;
                     }
                }
            }
        }
        <span class="hljs-keyword">return</span> T[<span class="hljs-number">0</span>][input.length-<span class="hljs-number">1</span>];
    }
    
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getSum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> freq[], <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span></span>{
        <span class="hljs-keyword">int</span> sum = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> x = i; x &lt;= j; x++){
            sum += freq[x];
        }
        <span class="hljs-keyword">return</span> sum;
    }
 
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        <span class="hljs-keyword">int</span> input[] = {<span class="hljs-number">10</span>,<span class="hljs-number">12</span>,<span class="hljs-number">20</span>,<span class="hljs-number">35</span>,<span class="hljs-number">46</span>};
        <span class="hljs-keyword">int</span> freq[] = {<span class="hljs-number">34</span>,<span class="hljs-number">8</span>,<span class="hljs-number">50</span>,<span class="hljs-number">21</span>,<span class="hljs-number">16</span>};
        OptimalTreeSearch ots = <span class="hljs-keyword">new</span> OptimalTreeSearch();
        System.out.println(ots.minCost(input, freq));
        System.out.println(ots.minCostRec(input, freq));
    }
}
</div></code></pre>

    </body>
    </html>